package mo.tags.stack;

import java.util.HashSet;
import java.util.Set;
import java.util.Stack;

public class L1249 {

    public String minRemoveToMakeValid(String s) {
        Stack<Pair> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == '(') {
                stack.push(new Pair(i, '('));
            } else if (s.charAt(i) == ')') {
                if (!stack.isEmpty() && stack.peek().c == '(') {
                    stack.pop();
                } else {
                    stack.push(new Pair(i, ')'));
                }
            }
        }
        if (stack.isEmpty()) {
            return s;
        }
        Set<Integer> idxList = new HashSet<>();
        while (!stack.isEmpty()) {
            idxList.add(stack.pop().idx);
        }
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (!idxList.contains(i)) {
                builder.append(s.charAt(i));
            }
        }
        return builder.toString();
    }

    private static class Pair {
        private int idx;
        private char c;

        public Pair() {
        }

        public Pair(int idx, char c) {
            this.idx = idx;
            this.c = c;
        }
    }


    public static void main(String[] args) {
        L1249 test = new L1249();
        System.out.println(test.minRemoveToMakeValid("))(("));
    }




}
